package JZ_Offer.algorithm.sort;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;


/**
 * 最小的K个数
 *
 * 输入n个整数，找出其中最小的K个数。
 * 例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
 *
 * @Author piper
 * @Date 2019/12/27 10:05 上午
 */
public class JZ40_最小的K个数 {

    /**
     * 1 借助set集合排序 取出前k个数
     */
    private static Set<Integer> set = new HashSet<>();

    private static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (k > input.length) {
            return list;
        }
        for (int a : input) {
            set.add(a);
        }

        int a = 1;
        for (Integer i : set) {
            if (a > k) {
                break;
            }
            list.add(i);
            a++;
        }

        return list;
    }

    /**
     * 2 快速排序实现
     * 3 维护k长度的大顶堆
     */

    public static void main(String[] args) {
        System.out.println(GetLeastNumbers_Solution(new int[]{4, 5, 1, 6, 2, 7, 3, 8}, 4));
    }

}
